package com.jjlin.chapter_3;

import java.util.*;
public class CD177{
    //二叉树节点
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static HashMap<Integer, Node> creatNodeList(int[][] nums){
        HashMap<Integer, Node> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.putIfAbsent(nums[i][0], new Node(nums[i][0]));
            if(nums[i][1] != 0){
                map.putIfAbsent(nums[i][1], new Node(nums[i][1]));
                map.get(nums[i][0]).left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                map.putIfAbsent(nums[i][2], new Node(nums[i][2]));
                map.get(nums[i][0]).right = map.get(nums[i][2]);
            }
        }
        return map;
    }

    //获得节点的记录表，key存储该节点，value存储该节点的父亲节点
    public static HashMap<Node, Node> record(Node head){
        HashMap<Node, Node> map = new HashMap<>();
        if(head != null)
            map.put(head, null); //根节点的父亲为null
        setMap(head, map);
        return map;
    }

    public static void setMap(Node head, HashMap<Node, Node> map){
        if(head == null)
            return;
        if(head.left != null)
            map.put(head.left, head);
        if(head.right != null)
            map.put(head.right, head);
        setMap(head.right, map);
        setMap(head.left, map);
    }

    //在二叉树中找到两个节点的最近公共祖先
    public static Node queryLowestAncestor(HashMap<Node, Node> map, Node o1, Node o2){
        if(o1 == null || o2 == null)
            return null;
        HashSet<Node> path = new HashSet<>();
        while(map.containsKey(o1)){
            path.add(o1);
            o1 = map.get(o1);
        }
        while(!path.contains(o2)){
            o2 = map.get(o2);
        }
        return o2;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        HashMap<Integer, Node> map = creatNodeList(nums);
        Node head = map.get(root);
        HashMap<Node, Node> nodeMap = record(head);//得到记录表
        int num = sc.nextInt();
        while(num-- > 0){
            int o1 = sc.nextInt();
            int o2 = sc.nextInt();
            Node node1 = map.get(o1);
            Node node2 = map.get(o2);
            Node res = queryLowestAncestor(nodeMap, node1, node2);
            if(res != null)
                System.out.println(res.val);
        }
    }
}
